package main

import "fmt"

func main() {
	l1 := &ListNode{
		Val: 1,
		Next: &ListNode{
			Val: 2,
			Next: &ListNode{
				Val:  4,
				Next: nil,
			},
		},
	}

	l2 := &ListNode{
		Val: 1,
		Next: &ListNode{
			Val: 3,
			Next: &ListNode{
				Val:  4,
				Next: nil,
			},
		},
	}
	mer := mergeTwoLists(l1, l2)
	fmt.Println(mer)
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}

	if list2 == nil {
		return list1
	}

	l1 := list1
	l2 := list2

	h := &ListNode{}
	p := h
	for {
		if l1 == nil && l2 == nil {
			return h.Next
		}

		if l1 == nil && l2 != nil {
			p.Next = l2
			return h.Next
		}

		if l1 != nil && l2 == nil {
			p.Next = l1
			return h.Next
		}

		if l1.Val == l2.Val {
			p.Next = &ListNode{
				Val: l1.Val,
				Next: &ListNode{
					Val: l2.Val,
				},
			}
			l1 = l1.Next
			l2 = l2.Next
			p = p.Next.Next
			continue
		}

		if l1.Val > l2.Val {
			p.Next = &ListNode{
				Val: l2.Val,
			}
			l2 = l2.Next
		} else {
			p.Next = &ListNode{
				Val: l1.Val,
			}
			l1 = l1.Next
		}

		p = p.Next
	}
}

type ListNode struct {
	Val  int
	Next *ListNode
}
